{\magonebf 3.4 Queues (queue)  }

\decl  queue E 

{\bf 1. Definition}

An instance $Q$ of the parameterized data type \name\ is 
a sequence of elements of data type $E$, called the element 
type of $Q$. Elements are inserted at one end (the rear) and deleted at the 
other end (the front) of $Q$. The size of $Q$ is the length of the sequence, 
a queue of size zero is called the empty queue.


\bigskip
{\bf 2. Creation}

\create Q {}

creates an instance \var\ of type \name. \var\ is initialized with the empty 
queue.


\bigskip
{\bf 3. Operations}
\+\cleartabs & \hskip 2truecm & \hskip 4truecm &\cr
\+\op E     top    {}       
                            { returns the front element of \var}
\+\nop                      { \precond $Q$ is not empty.}
\smallskip
\+\op E     pop    {}       
                            { deletes and returns the front element of \var}
\+\nop                      { \precond $Q$ is not empty.}
\smallskip
\+\op void  append {E\ x}   
                            { appends $x$ to the rear end of \var.}
\smallskip
\+\op void  clear  {}       
                            { makes \var\ the empty queue.}
\smallskip
\+\op int   size   {}       
                            { returns the size of \var.}
\smallskip
\+\op bool  empty  {}       
                            { returns true if \var\ is empty, false otherwise.}
 
\bigskip
{\bf 4. Implementation}

Queues are implemented by singly linked linear lists. All operations take time 
$O(1)$, except clear which takes time $O(n)$, where $n$ is the size of the 
queue.


%\bigskip
%{\bf 5. Bounded Queues}
%
%Bounded queues (b\_queues) are queues of bounded size. 
%\medskip
%\+\cleartabs
%  Declaration: &{\bf declare}($b\_queue,E$) \cr
%\+Creation:    &$b\_queue(E)$ $Q(n)$; \cr
%\+             &creates an instance $Q$ of type $b\_queue(E)$ that can hold up to $n$ elements.\cr
%\+Operations:  &see queue\cr
%
